package top.minuy.subject.leetcode._187;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 使用滚动哈希方法求解
 * <p>
 * 187. 重复的DNA序列
 * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * <p>
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 * 输出：["AAAAACCCCC","CCCCCAAAAA"]
 * 示例 2：
 * <p>
 * 输入：s = "AAAAAAAAAAAAA"
 * 输出：["AAAAAAAAAA"]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= s.length <= 105
 * s[i] 为 'A'、'C'、'G' 或 'T'
 *
 * @author Minuy
 * @time 9:34
 * @date 2021/11/13
 */
public class Solution2 {
    public List<String> findRepeatedDnaSequences(String s) {
        if(s.length()<11){
            return new ArrayList<String>();
        }
        final List<String> ans = new ArrayList<String>();
        final char[] bin = new char['T' + 1];

        bin['A'] = 0;
        bin['C'] = 1;
        bin['G'] = 2;
        bin['T'] = 3;

        int hash = 0;
        for (int i = 0; i < 9; i++) {
            hash = (hash << 2) + bin[s.charAt(i)]; // hash << 2 = hash * (2**2)
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 9; i < s.length(); i++) {

            hash = (hash << 2) + bin[(s.charAt(i))];
            map.put(hash, map.getOrDefault(hash, 0) + 1);
            if (map.get(hash) == 2) {
                ans.add(s.substring(i - 9, i + 1));
            }

            // bin[s.charAt(i - 9)] << 18 = bin[s.charAt(i - 9)] * (2**18)
            hash = hash - (bin[s.charAt(i - 9)] << 18);

        }
        return ans;
    }
}
